這道題的目的是判斷一個單向鏈結串列是否是回文。

題目：
給定一個單向鏈結串列，判斷該鏈結串列是否為回文結構。換句話說，鏈結串列中的節點值從前往後和從後往前是相同的。

範例：

輸入: 1 -> 2
輸出: false

輸入: 1 -> 2 -> 2 -> 1
輸出: true

解題思路

解法1: stack
先將 list 元素複製到 stack 中，再利用 stack 後進先出特性再從新遍歷一次 list 同時一一比較 stack 裡的元素，

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> stk;
        ListNode* curr = head;
        while (curr != nullptr) {
            stk.push(curr->val);
            curr = curr->next;
        }

        curr = head;
        while (curr != nullptr) {
            if (stk.top() != curr->val)
                return false;
            stk.pop();
            curr = curr->next;
        }
        return true;
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

解法2: 陣列+two pointer
先將 list 元素複製到陣列中，在使用 two pointer 分別從頭尾開始檢查是否為回文，

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vec;
        ListNode* curr = head;
        while (curr != nullptr) {
            vec.push_back(curr->val);
            curr = curr->next;
        }

        int left = 0;
        int right = vec.size() -1;
        while (left < right) {
            if (vec[left] != vec[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

解法3:快慢指標
用快慢指標找到中間點，再將後半部反轉，接著比對前半部跟後半部是否為回文，

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 用快慢指標找到中間點
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // slow 是中間點, 接著反轉 slow 的下半部
        ListNode* prev = nullptr;
        while (slow != nullptr) {
            ListNode* tmp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = tmp;
        }

        // 比較上半部跟下半部
        // right 下半部長度是等於或小於 left 前半部的長度
        ListNode* left = head;
        ListNode* right = prev;
        while (right != nullptr) {
            if (left->val != right->val)
                return false;
            left = left->next;
            right = right->next;
        }

        return true;
    }
};

時間複雜度：O(n)
空間複雜度：O(1)

參考：
#234. Palindrome Linked List